1. Field of the Invention
The present invention relates to a packet relay device in networks.
2. Description of the Related Art
Packet relay devices include functions, such as filtering and QoS (Quality of Service), for specifying a process in association with each flow (for example, paragraph 0002 of JP-3936883-B1). A flow is an aggregation of packets that are identified based on conditions, such as input line numbers of packets and values of packet headers. To realize this function, upon reception of packets, the packet relay device executes a flow search for searching to which flow the received packets belong, and determines which process is to be performed for the packets.
Further, with the development of the packet relay devices, the flow search is required by a plurality of functions, in addition to the filtering and QoS. Examples of the functions include a monitoring function, such as mirroring and a flow statistics function (for example, paragraph 0005 of JP-2012-34192-A).
As described above, the packet relay devices tend to have many functions requiring the flow search. Thus, it is required to realize a high-speed technology of the flow search, not to lower the performance of the flow search, even if the number of these functions increases. Conventionally, the flow search has been realized at high speed by a CAM search using a search dedicated memory, so-called a CAM (Content Addressable Memory, associative memory) (JP-3936883-B1).
JP-2012-34192-A discloses a packet transfer device which has a CAM control unit, a CAM, a RAM control unit, and RAM. Specifically, a flow search CAM control unit 613 searches a flow search CAM 614 for a predetermined block, using at least one information item of header information items of received packets, as a search key, and executes a flow search for identifying a flow to which the packets belongs. For example, the flow search CAM control unit 613 executes a flow search for a block of the flow search CAM 614 which has been specified with reference to a search activation flag table 612. A flow process RAM control unit 615 searches flow process RAM 616, based on a hit address which has been obtained as a result of the flow search by the flow search CAM control unit 613. The flow process RAM 616 stores information regarding a flow process at an address corresponding to the flow search CAM 614. A flow process determining unit determines a flow process, based on the search result by the flow search CAM control unit 613 and the flow process RAM control unit 615.
When there are a plurality of flow entries matching with a CAM, the CAM preferentially outputs an address of a flow entry which is stored at a preceding address with a small value. Subsequently, a direction in which address values get small is called “preceding”, a direction in which address values get large is called “following”, a consecutive address range is called “an address space”, an address with the smallest address value in the address space is called a “lower limit address”, and an address with the largest address value in the address space is called an “upper limit address”.
RAM (Random Access Memory) registers action entries with a description of a process to be performed for flows matching with the flow entries of addresses in the CAM. An acquired address in the CAM as a search result is converted into a read address of the RAM by the RAM control unit to read the RAM. By doing this, a determination is made as to which process is to be performed for the corresponding flow.
If the number of functions requiring the flow search increases, a table with registered flow conditions corresponding to the functions is stored in the CAM, in association with the increased number of functions. It is necessary to execute the flow search for the increased number of functions for one packet. Thus, the increase in the time of the flow search deteriorates the processing performance per packet.
U.S. Pat. No. 6,629,099 discloses a technique for solving this problem. According to this technique, there is provided a CAM which can execute a plurality of searches at the same time in response to one search command. Thus, even if the number of functions requiring the flow search increases, the flow search performance is not deteriorated. When the plurality of searches are executed in response to one search command, a plurality of search results can be obtained per search command.
However, in a CAM search, it is necessary to determine which process is to be performed for a corresponding flow, by reading the RAM in accordance with a search result. When the plurality of searches are executed in accordance with one search command, it is necessary to read the RAM for the plurality of search results. Thus, as the number of searches increases, the reading performance of the RAM will be a bottleneck. This causes a problem that the performance of the flow search is deteriorated.
This is because the RAM cannot output simultaneously all read commands acquired as a result of CAM search. In addition, the RAM outputs each read result in response thereto, thereafter performing a process for a next read command. That is, the RAM sequentially outputs read results in response to a plurality of read commands. The RAM cannot start a next process for packets, until the plurality of read results are completely output. Therefore, according to the technique of U.S. Pat. No. 6,629,099, even if the CAM search time is reduced, the time is not reduced in the RAM, thus lowering the performance of the flow search.